def make_mat(m, n, fill=None):
    mat = []
    for i in range(m):
        mat.append([fill] * n)
    return mat


def show(b, c):
    n = len(b)
    m = len(b[0]) - 1
    i = n - 1
    j = m
    has = []
    while i >= 0:
        k = b[i][j]
        if c[i][j] > c[i-1][k]:
            has.append(i)
        i -= 1
        j = k
    return has


def pack(w, v, m):
    n = len(w)
    b = make_mat(n, m+1, fill=0)
    c = make_mat(n, m+1, fill=0)

    for i in range(n):
        for j in range(m+1):
            if j < w[i]:
                c[i][j] = c[i - 1][j]
                b[i][j] = j
            elif c[i-1][j-w[i]] + v[i] > c[i-1][j]:
                c[i][j] = c[i-1][j-w[i]] + v[i]
                b[i][j] = j-w[i]
            else:
                c[i][j] = c[i-1][j]
                b[i][j] = j

    return show(b, c), c[n-1][m]


def frac(w, v, m):
    n = len(w)
    items = []
    for i in range(n):
        items.append([float(w[i]), float(v[i]), float(w[i]) / v[i]])
    reversed(sorted(items, key=lambda x: x[2]))

    val = 0
    for item in items:
        if item[0] <= m:
            val += item[1]
            m -= item[0]
        else:
            val += item[1] * (m / item[0])
            m -= item[0]
    return val

if __name__ == '__main__':
    w = [10, 20, 30, 40, 50]
    v = [20, 30, 65, 40, 60]
    m = 100
    print(pack(w, v, m))
    print(frac(w, v, m))
